//1.逐行二分-------最坏情况 O(m logn)
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        for(int i=0;i<m;++i) {
            int left =0;
            int right = n-1;
            if(!(matrix[i][0]<=target && target <= matrix[i][n-1])) continue;
            while(left<=right) {
                int mid = (right-left)/2 + left;
               
                int val = matrix[i][mid];
                if(target<val)
                    right = mid-1;
                else if(target> val)
                    left = mid+1;
                else    
                    return true;
            }
        }
        return false;


    }
};



//2  Z字形判断------O(m+n)---右上角做法
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int row = 0, col = n - 1;

        while (row < m && col >= 0) {
            int val = matrix[row][col];
            if (val == target) return true;
            else if (val > target) col--;
            else row++;
        }
        return false;
    }
};
//3  Z字形判断------O(m+n)---左下角做法
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int row = m-1, col = 0;

        while (col < n && row >= 0) {
            int val = matrix[row][col];
            if (val == target) return true;
            else if (val > target) row--;
            else col++;
        }
        return false;
    }
};
/*
左上和右下角不行：左上是右移动和下移动都增加，写不了怎么走
                右下是左移动和上移动都减少，写不了怎么走

左下和右上刚好都有一个是增加一个减少，不断地排除


*/

